#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


void genShuff(vector<string> &str, int n)
{
    for (int i = 0; i < n; i++) {
        char ch = '0' + i;
        string tmp = "a";
        tmp += ch;
        str.push_back(tmp);
    }
    for (int i = 0; i < n; i++) {
        char ch = '0' + i;
        string tmp = "b";
        tmp += ch;
        str.push_back(tmp);
    }
}

void swap(string &a, string &b)
{
    string tmp = a;
    a = b;
    b = tmp;
}

void reverse(vector<string>::iterator start, vector<string>::iterator end)
{
    while (start < end) {
        swap(*start, *end);
        start++;
        end--;
    }
}

void printArr(const vector<string> &test1)
{
   for (int i = 0; i < test1.size(); i++)
        cout << test1[i];
    cout << endl;
}

int target(int i, int length)
{
	if (i%2 == 1)
		return length/2 + i/2;
	else 
		return i/2;
}

void arrayShuffle(vector<string> &v, int first, int last) {
    if (v.size()%2 != 0)
		return;

	for (int i = 1; i < v.size()-2; i++) {
		int targetIndex = target(i, v.size());
		while (targetIndex < i) {
			targetIndex = target(targetIndex, v.size());
		}
		if (i != targetIndex)
			swap(v[i], v[targetIndex]);
		//printArr(v);
	}
}

int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    vector<string> test1;
    genShuff(test1, 5);
    for (int i = 0; i < test1.size(); i++)
        cout << test1[i];
    cout << endl;

    arrayShuffle(test1, 0, test1.size()-1);
    printArr(test1);

}
